package arithmetic2.day07;

import java.util.*;

/*
    图
 */
public class Graph {
    //当前图的所有点集
    public HashMap<Integer, Node> nodes;
    //当前图的所有边集
    public HashSet<Edge> edges;

    public Graph() {
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }

    /*
        将某个点作为开始节点做宽度优先遍历:
            1.准备一个队列和一个无序列表
            2.将开始节点放入到队列和列表中
            3.如果队列不为空，将队列一个节点出队列，并打印
            4.将这个节点的所有子节点依次加入到队列和列表中(已经添加的节点无需添加)
            5.重复3、4操作,直到队列为空
     */
    public void bfs(int key) {
        //获取当前节点
        Node node = nodes.get(key);
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        Set<Node> set = new HashSet<>();
        //将当前节点添加到队列和列表中
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()) {
            //将当前节点出队列
            Node curNode = queue.poll();
            //处理当前节点
            System.out.println(curNode.value);
            //将当前节点的所有子节点加入到队列和列表中
            for (Node n : curNode.nexts) {
                if (!set.contains(n)) {    //这个节点没有被处理过
                    queue.add(n);
                    set.add(n);
                }
            }
        }
    }

    /*
        将某个点作为开始点做深度优先遍历:
            1.准备一个栈和一个无序列表
            2.将当前节点放入栈和列表中，将当前节点出栈
            3.拿到当前出栈节点的所有子节点，将当前节点再入栈，将第一个没有处理过的子节点也入栈和列表，并处理该子节点
            4.重复上述2、3操作，直到所有节点都处理完
     */
    public void dfs(int key) {
        Node node = nodes.get(key);
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        //将当前节点入栈和列表
        stack.push(node);
        set.add(node);
        System.out.println(node.value);
        while (!stack.isEmpty()) {
            //将当前节点出栈
            Node curNode = stack.pop();
            //得到当前节点的所有子节点
            ArrayList<Node> nexts = curNode.nexts;
            //将第一个没有处理过的子节点按步骤3操作
            for (Node n : nexts) {
                if (!set.contains(n)) {
                    //将当前节点再入栈
                    stack.push(curNode);
                    //将第一个没有处理过的子节点入栈和列表，并处理
                    stack.push(n);
                    set.add(n);
                    System.out.println(n.value);
                    break;
                }
            }
        }
    }

    /*
        将一个没有循环依赖的图做拓扑排序:
            1.将图中入度为0的点处理
            2.将这些入度为0的点及其影响删除
            3.重复1、2操作,直到所有点都处理完毕
     */
    public void sortedTopology() {
        while (!nodes.isEmpty()) {
            //得到图中所有入度为0的点
            List<Node> inZeros = new ArrayList<>();
            for (Integer key : nodes.keySet()) {
                if (nodes.get(key).in == 0) {
                    inZeros.add(nodes.get(key));
                }
            }
            //将所有入度为0的点及其影响删除
            for (Node node : inZeros) {
                //处理这个点
                System.out.println(node.value);
                //将这个点的影响删除
                ArrayList<Node> nexts = node.nexts;
                //将这个点的所有子节点的入度-1
                for (Node n : nexts) {
                    n.in--;
                }
                //删除这个点
                nodes.remove(node.value);
            }
        }
    }

    /*
        将图转换为最小生成树(克鲁斯卡尔算法):
            1.每次选择最小的边连接两个点
            2.如果加入这个边之后与之前的边形成了环，就不能要这条边
            3.重复1、2操作，直到所有的边都加入过了
     */
    public Graph kruska() {
        //创建一个新的图返回
        Graph graph = new Graph();
        //将所有节点复制一份,添加到新图中
        for(Integer value:nodes.keySet()){
            graph.nodes.put(value,new Node(value) );
        }
        //将边放到list中，用以排序
        List<Edge> edgeList = new ArrayList<>();
        for(Edge edge : edges){
            edgeList.add(edge);
        }
        //排序
        Collections.sort(edgeList);
        //创建判断是否形成环的数据结构
        MySet mySet = new MySet(graph.nodes);
        //从最小的边开始遍历,依次添加到新图中
        for(Edge edge:edgeList){
            if(!mySet.isSameSet(edge.from,edge.to)){ //这两个点不在一个集合中,才能添加这个边
                //创建一个新的边添加到新图中
                Edge newEdge = new Edge(edge.weight);
                Node fromNode = new Node(edge.from.value);
                Node toNode = new Node(edge.to.value);
                newEdge.from = fromNode;
                newEdge.to = toNode;
                graph.edges.add(newEdge);
                //将两个点所拥有的集合合并
                mySet.union(fromNode,toNode);
            }
        }
        return graph;
    }

    /*
        用来判断是否形成环的数据结构
     */
    public static class MySet {
        //存储每个点拥有的集合
        public Map<Node, List<Node>> setMap = new HashMap<>();

        /*
            通过点集将setMap初始化
         */
        public MySet(Map<Integer,Node> nodes) {
            for (Integer value : nodes.keySet()) {
                Node node = nodes.get(value);
                //初始每个点拥有的集合里面自有自己
                ArrayList<Node> list = new ArrayList<>();
                list.add(node);
                setMap.put(node, list);
            }
        }

        /*
            判断两个点是否在一个集合中
         */
        public boolean isSameSet(Node from, Node to) {
            //拿到两个点各自的集合
            List<Node> fromList = setMap.get(from);
            List<Node> toList = setMap.get(to);
            //如果两个点的集合是同一个，就代表在一个集合中
            return fromList == toList;
        }

        /*
            合并两个点各自拥有的集合
         */
        public void union(Node from,Node to){
            //拿到两个点各自的集合
            List<Node> fromList = setMap.get(from);
            List<Node> toList = setMap.get(to);
            for(Node toNode:toList){
                //将节点添加到另一个集合
                fromList.add(toNode);
                //并将这个节点的集合变为fromList
                setMap.put(toNode,fromList);
            }
        }
    }


}
